1. Field of the Invention
This invention relates to caches.
2. Related Art
When a client device seeks to obtain information from server devices on a network, it is sometimes desirable to provide a cache, that is, a device which maintains copies of that information so that multiple requests for the same information can be satisfied at the cache, and do not require that information to be transmitted repeatedly across the network. Known caches do this to reduce the amount of communication bandwidth used between the clients and the servers, and when shared by more than one client, act to reduce the total amount of communication bandwidth used between all of the clients and the servers.
One problem in the art is that information requested a second time (possibly requested a second time by the same client, or requested by a second client after a first client has already requested that information once) can change at the server between the time it is first requested and the time it is requested again. In such cases, transmitting the stored information from the cache gives inaccurate information to the second requester. This can reduce the confidence users at the client devices have for the information provided by the cache.
One known method is to transmit each request from the client device to the server, so as to obtain an answer as to whether the document must be refreshed before it is served (transmitted) to the client device. While this method achieves the purpose of serving only refreshed information to the client device, it has the drawback that the client device must wait for contact with the server device and the reply from the server device, even when the information is already present in the cache. Moreover, this method uses communication bandwidth by sending requests to the server device and receiving confirmations from the server device which can be unnecessary.
It would be advantageous to provide a cache which reduces the average amount of time users at the client device wait for information, rather than attempting to reduce the amount of communication bandwidth between the client devices and the server devices. One aspect of the invention is to automatically refresh the information maintained in the cache, notwithstanding that this uses additional communication bandwidth. The cache occasionally queries the server device to determine if the document has been changed, so the cache can maintain an up-to-date version of the document. When the document is requested by the client device, the cache serves that document immediately without checking with the server device.
Refreshing information in the cache is useful, but some documents require refresh more often than others. If a particular document is selected for refresh less often than required, it will sometimes be served to the client device even though it is "stale" (that is, modified at the server since the cache last obtained a copy). In contrast, if a particular document is selected for refresh more often than required, the document will sometimes be refreshed unnecessarily, thus wasting communication bandwidth.
Accordingly, it would be advantageous to provide a method and system for refreshing documents so that each particular document is refreshed no more often and no less often than needed. This advantage is achieved in a system in which the times for refresh are tailored to each particular document, in response to both an estimated probability distribution of times for client requests for that document and an estimated probability distribution of times for server changes to that document.
Another problem in the art is that it is difficult to objectively determine the value the cache is providing for the system including the cache, or whether the cache is too small or too large. In contrast with persistent storage devices, for which it is easy to determine how full they are and whether the size of the storage device is too small or too large, the cache is nearly always nearly full of data being stored for later request by the client device.
One known method to determine the value of the cache is to measure the cache "hit rate," that is, the fraction of information requests which are for documents already maintained in the cache. However, this measure is extremely dependent on the degree of locality of reference to information requested by the client device, which in turn is extremely dependent on the number of client devices, the nature of information they are requesting, and the rate at which they request that information.
Accordingly, it would be advantageous to provide a method and system for objectively estimating the value the cache is providing for the system including the cache, such as whether the cache is too small or too large for selected objectives. This advantage is achieved in a system in which the cache estimates for each document a probability distribution of times for client requests for that document, and determines a cumulative probability distribution which reflects the estimated marginal hit rate at the storage limit of the cache and the marginal advantage of adding storage to the cache.